package io.renren.modules.demo.algorithm;

import java.util.ArrayList;

public class Inherit
{
    public static void Cross(Chromosome chromosome1, Chromosome chromosome2)
    {
        int length = chromosome1.getChromosome().size();
        int begin = (int)(Math.random() * (length - 1));
        int end = (int)(Math.random() * (length - 1 - begin)) + begin + 1;
        for(int i = begin; i <= end; i++)
        {
            Gene temp = chromosome1.getChromosome().get(i);
            chromosome1.getChromosome().set(i, chromosome2.getChromosome().get(i));
            chromosome2.getChromosome().set(i, temp);
        }
        Chromosome chromosome1Copy = new Chromosome(chromosome1.getChromosome());
        int[] arr1 = new int[length + 1];
        int[] arr2 = new int[length + 1];

        for(int i = 0; i < length + 1; i++)
        {
            arr1[i] = 0;
        }
        for(int i = begin; i <= end; i++)
        {
            arr1[chromosome1.getChromosome().get(i).getSerialNumber()]++;
        }
        while(true)
        {
            int sameNumber = 0;
            for (int i = 0; i < length; i++)
            {
                if (i >= begin && i <= end)
                    continue;
                if (arr1[chromosome1.getChromosome().get(i).getSerialNumber()] == 0)
                    arr1[chromosome1.getChromosome().get(i).getSerialNumber()]++;
                else
                {
                    sameNumber++;
                    for (int j = begin; j <= end; j++)
                    {
                        if (chromosome1.getChromosome().get(j).getSerialNumber() == chromosome1.getChromosome().get(i).getSerialNumber())
                        {
                            chromosome1.getChromosome().set(i, chromosome2.getChromosome().get(j));
                            break;
                        }
                    }
                }
            }
            if(sameNumber == 0)
                break;
            else
            {
                for(int i = 0; i < length + 1; i++)
                {
                    arr1[i] = 0;
                }
                for(int i = begin; i <= end; i++)
                {
                    arr1[chromosome1.getChromosome().get(i).getSerialNumber()]++;
                }
            }
        }

        for(int i = 0; i < length + 1; i++)
        {
            arr2[i] = 0;
        }
        for(int i = begin; i <= end; i++)
        {
            arr2[chromosome2.getChromosome().get(i).getSerialNumber()]++;
        }
        while(true)
        {
            int sameNumber = 0;
            for (int i = 0; i < length; i++)
            {
                if (i >= begin && i <= end)
                    continue;
                if (arr2[chromosome2.getChromosome().get(i).getSerialNumber()] == 0)
                    arr2[chromosome2.getChromosome().get(i).getSerialNumber()]++;
                else
                {
                    sameNumber++;
                    for (int j = begin; j <= end; j++)
                    {
                        if (chromosome2.getChromosome().get(j).getSerialNumber() == chromosome2.getChromosome().get(i).getSerialNumber())
                        {
                            chromosome2.getChromosome().set(i, chromosome1Copy.getChromosome().get(j));
                            break;
                        }
                    }
                }
            }
            if(sameNumber == 0)
                break;
            else
            {
                for(int i = 0; i < length + 1; i++)
                {
                    arr2[i] = 0;
                }
                for(int i = begin; i <= end; i++)
                {
                    arr2[chromosome2.getChromosome().get(i).getSerialNumber()]++;
                }
            }
        }
        chromosome1.CalculateFitness();
        chromosome2.CalculateFitness();
    }

    public static Population GenerateChildrenPopulation(Population population, double GGAP, double crossRate)  //原种群中共有GGAP*Size个个体被替换
    {
        double maxFitness = 0;
        int index = 0;
        for(int j = 0; j < population.getPopulation().size(); j++)
        {
            if(population.getPopulation().get(j).getFitness() > maxFitness)
            {
                maxFitness = population.getPopulation().get(j).getFitness();
                index = j;
            }
        }
        Chromosome bestChromosome = population.getPopulation().get(index);

        ArrayList<Chromosome> childrenPopulation = new ArrayList<>();
        ArrayList<Double> sumProbability = new ArrayList<>();
        sumProbability.add(population.getPopulation().get(0).getFitness() / population.getFitnessSum());
        for(int i = 1; i < population.getPopulation().size(); i++)
        {
            double probability = population.getPopulation().get(i).getFitness() / population.getFitnessSum();
            sumProbability.add(sumProbability.get(i - 1) + probability);
        }
        //按轮盘赌算法抽取父母繁衍GGAP*Size个子代，并进行交叉和变异，再用轮盘赌选择（1 - GGAP）* Size - 1个父母直接加入子代，最强者直接加入子代
        while(childrenPopulation.size() < GGAP * population.getPopulation().size())
        {
            double random1 = Math.random();
            double random2 = Math.random();
            double random = Math.random();
            if(random <= crossRate)
            {
                Chromosome chromosome1Copy = new Chromosome(population.getPopulation().get(BinarySearch(sumProbability, random1)));
                Chromosome chromosome2Copy = new Chromosome(population.getPopulation().get(BinarySearch(sumProbability, random2)));
                Cross(chromosome1Copy, chromosome2Copy);
                childrenPopulation.add(chromosome1Copy);
                childrenPopulation.add(chromosome2Copy);
            }
            else
            {
                childrenPopulation.add(population.getPopulation().get(BinarySearch(sumProbability, random1)));
                childrenPopulation.add(population.getPopulation().get(BinarySearch(sumProbability, random2)));
            }
        }
        childrenPopulation.add(bestChromosome);
        for(int i = 0; i < (1 - GGAP) * population.getPopulation().size() - 1; i++)
        {
            double random = Math.random();
            childrenPopulation.add(population.getPopulation().get(BinarySearch(sumProbability, random)));
        }
        return new Population(childrenPopulation);
    }

    public static int BinarySearch(ArrayList<Double> sumProbability, double random)
    {
        int begin = 0;
        int end = sumProbability.size() - 1;
        while(begin <= end)
        {
            int mid = (begin + end) / 2;
            if(sumProbability.get(mid) <= random)
            {
                begin = mid + 1;
            }
            else
            {
                if( mid == 0 || sumProbability.get(mid - 1) <= random)
                {
                    return mid;
                }
                else
                {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}
